/**
 * @ClassName chapter1.KP4_selectsort
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/7 14:24
 */

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class KP3_bubblesort {

    /**
     * 需要考虑数组下标越界
     */
    public static void bubbleSort_0(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int N = array.length;
       for (int i = 0; i < N; i++) {
           // 0 ~ N - 1
           // 01 12 23 ..
           for (int j = 0; j < N - 1 -i; j++) {
               if (array[j+1] < array[j]) {
                   swap(array,j,j+1);
               }
           }
       }
    }

    /**
     * 对bubbleSort_0的优化，考虑到已经有序的数组不需要在排序了
     */
    public static void bubbleSort_1(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int N = array.length;
        for (int i = 0; i < N; i++) {
            boolean flag = false;
            // 0 ~ N - 1
            // 01 12 23 ..
            for (int j = 0; j < N - 1 -i; j++) {
                if (array[j+1] < array[j]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if (flag == false) break;
        }
    }

    /**
     * 不需要考虑数组下标越界的情况
     */
    public static void bubbleSort_2(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int N = array.length;
        for (int end = N -1; end >= 0; end--) {
            // 0 ~ N - 1
            // 01 12 23 ..
            for (int second = 1; second <= end; second++) {
              if (array[second] < array[second-1]) {
                  swap(array,second,second-1);
              }
            }
        }
    }

    /**
     * 对bubbleSort_2的优化，考虑到已经有序的数组不需要在排序了
     */
    public static void bubbleSort_3(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int N = array.length;
        for (int end = N -1; end >= 0; end--) {
            boolean flag = false;
            // 0 ~ N - 1
            // 01 12 23 ..
            for (int second = 1; second <= end; second++) {
                if (array[second] < array[second-1]) {
                    swap(array,second,second-1);
                    flag = true;
                }
            }
            if (flag == false) break;
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2,4,1,5,17,15,86};
        System.out.println(Arrays.toString(array));
        //bubbleSort_0(array);
        //bubbleSort_1(array);
        //bubbleSort_2(array);
        bubbleSort_3(array);
        System.out.println(Arrays.toString(array));
    }


}
